package maxscorebutminlevel

// prefix sum
func minimumLevels(possible []int) int {
	// 没通过关卡n，通过这个关卡的得分是固定的
	total := 0
	for _,v := range possible {
		total += v   
	}
	// 计算最终总得分，目前total是1的数量
	n := len(possible)
	// 最终得分：
	// total = total - (n-total) //sumOfZero := n - total;  
	total = 2*total -n   

	pre := 0   // alice得分     bob: total-pre
	// pre > total -pre  =>   2*pre > total
	for i:=0;i<n-1;i++ {  // 每个玩家至少完成一个关卡
		if(possible[i] == 1) {
			pre ++
		} else {
			pre--;
		}
		if 2* pre > total {
			return i+1;
		}
	}
	return -1;
}
